// @algorithm @lc id=1832 lang=cpp 
// @title minimum-operations-to-make-a-subsequence


// #define print(...)
// @test([5,1,3],[9,4,2,3,4])=2
// @test([6,4,8,1,3,2],[4,7,6,2,3,8,6,1])=3
class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int,int> ti; // <target各值, 在target中的索引>
        for(int i=0; i<target.size(); i++)
            ti[target[i]] = i;
        vector<int> ai; // target 各值在 arr 中的索引(升序)
        for(auto & a : arr){
            auto tx = ti.find(a);
            if(tx == ti.end()) continue;
            auto ax = lower_bound(ai.begin(), ai.end(), tx->second);
            if(ax != ai.end())
                *ax = tx->second;
            else
                ai.push_back(tx->second);
        }
        return target.size() - ai.size();
    }
};